package 链表与双指针.m03.d13.t02;

import 链表与双指针.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode node = new ListNode();
        node.next = head;
        ListNode pre = node, tail = node;
        while (tail.next != null) {
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                if (tail == null) {
                    return node.next;
                }
            }
            ListNode nex = tail.next;
            ListNode[] nodes = reverse(head, tail);
            head = nodes[0];
            tail = nodes[1];
            pre.next = head;
            tail.next = nex;
            pre = tail;
            head = nex;
        }
        return node.next;
    }

    public ListNode[] reverse(ListNode head, ListNode tail) {
        ListNode pre = tail.next, cur = head;
        while (pre != tail) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return new ListNode[] { tail, head };
    }
}